package com.chao.search;

import java.util.Arrays;

/**
 * @author : Rookie
 * @description : 斐波那契查找
 * @date : 2023/7/3
 */
public class FibonacciSearch {

    public static void main(String[] args) {
        int[] arr = new int[] {0,2,5,6,8,13,35,41};
        int target = 8;
        int result = search(arr, target);
        System.out.println(result);
    }

    private static int search(int []arr,int target) {
        // 生成斐波那契数列
        int[] fib = getFibonacciSequence(arr.length);
        // 表示斐波那契数列中第k个元素作为分割点
        int k = 0;
        while (fib[k] - 1 < arr.length) {
            k++;
        }

        // 创建临时数组，并将arr数组拷贝进去，保证最后一位填充为原数组的最后一个元素，用于查找边界处理
        int[] temp = new int[fib[k] - 1];
        System.arraycopy(arr, 0, temp, 0, arr.length);
        int lastValue = arr[arr.length - 1]; // 暂存原数组最后一个元素的值

        // 扩展temp数组的长度，用lastValue填充
        for (int i = arr.length; i < fib[k] - 1; i++) {
            temp[i] = lastValue;
        }
        int left = 0,right = arr.length - 1,index = -1;
        while (left < right) {
            int mid = left + fib[k-1] - 1;
            if (temp[mid] > target) {
                right = mid - 1;
                k-=1;
            } else if (temp[mid]<target){
                left = mid + 1;
                k-=2;
            } else {
                // 找到目标值
                if (mid <= right) {
                    index = mid;
                } else {
                    // 当补全元素是真实数据时，说明查找到了补全的元素，即为原数组最后一个元素
                    index = right;
                }
                break;
            }
        }
        return index;
    }

    private static int[] getFibonacciSequence(int n) {
        int[] fibArr = new int[n];
        fibArr[0] = 1;
        fibArr[1] = 1;
        for (int i = 2; i < n; i++) {
            fibArr[i] = fibArr[i-1] + fibArr[i - 2];
        }
        return fibArr;
    }
}
